package service.impl;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import bean.Distance;
import bean.Graph;
import bean.Point;

public class Dijkstra {
	private Graph	graph;
	private float[]	disValue;
	private int[]	shortest;
	private int		start;
	private int[]	seq;		// 用来存储start到end的路径。
	private int[]	validPoint;

	private int[] getSeq() {
		List<Integer> ints = new ArrayList<Integer>();
		for (int i : seq)
			if (i != -1)
				ints.add(i);
		int[] t = new int[ints.size()];
		for (int i = 0; i < t.length; i++) {
			t[i] = ints.get(i).intValue();
		}
		seq = t;
		for (int i = 0; i < seq.length / 2; i++) {
			int temp = seq[i];
			temp = seq[i];
			seq[i] = seq[seq.length - 1 - i];
			seq[seq.length - 1 - i] = temp;
		}
		return seq;
	}
	private void setStart(int start) {
		this.start = start;
	}

	private Dijkstra(Graph g, int[] validPoint) {
		this.validPoint = validPoint;
		this.graph = g;
		disValue = new float[graph.size() + 1];
		shortest = new int[graph.size() + 1];
		seq = new int[shortest.length];
	}

	private void initializeSingleSource() {
		for (int i = 1; i <= graph.size(); i++) {
			disValue[i] = -1; // -1 is the maximum value
			shortest[i] = 0;
		}
		for (int i = 0; i < seq.length; i++) { // 用来存储start到end的路径。
			seq[i] = -1;
		}

	}

	private void shortestPath(int start, int end) {
		setStart(start);
		initializeSingleSource();
		disValue[start] = 0; // 定义起点的位置
		LinkedList<Integer> s = new LinkedList<Integer>();
		LinkedList<Integer> q = new LinkedList<Integer>();

		for (int i = 1; i <= graph.size(); i++) {
			int temp = 0;
			while (temp != validPoint.length) {
				if (validPoint[temp] == i) {
					q.add(i);
					break;
				}
				temp++;
			}

		}

		while (q.size() != 0) {

			ListIterator<Integer> iteratorQ = q.listIterator();
			ListIterator<Integer> iterator = null;
			float mindis = -1; // 最近的距离
			int minpos = -1; // 最近的点的序号

			while (iteratorQ.hasNext()) { // 确定起点到已知路径的哪个点最近。
				int current = iteratorQ.next();

				if (disValue[current] != -1 /* 起点到目前的距离不为无穷大 */
						&& (mindis == -1 || disValue[current] < mindis)
				/* 起点到目前位置的距离小于新求的距离或者最小的距离尚未求得的时候 */) {
					mindis = disValue[current];
					minpos = current;
				}
			}
			// if (minpos != -1) {
			q.remove(q.indexOf(minpos)); // 移除

			s.add(minpos); // 添加

			iterator = graph.getChainByIndex(minpos).listIterator(); // 取出最近点的邻居们

			while (iterator.hasNext()) {
				int minposNei = iterator.next();
				float newDis = disValue[minpos]
						+ graph.getDistence(minpos, minposNei);
				if (disValue[minposNei] == -1 || disValue[minposNei] > newDis) {
					// 如果到该邻居的距离尚未算得，或者已算得的比这次算得大,则替换掉
					disValue[minposNei] = newDis;
					shortest[minposNei] = minpos; // 表示到minposNei
													// 最近要经过minpos
				}
			}
			// }
			// else{

			// }
		}

		// 显示路径和距离
		showPath(end, 0);
	}

	private void showPath(int end, int count) {

		if (end != start) {
			seq[count] = end;
			count++;
			end = shortest[end];
			showPath(end, count);
		} else {
			seq[count] = end;
		}

	}
	
	public static List<Point> doDijkstra(List<Distance> dis, Point start, Point end) {
		Set<Point> points = new HashSet<Point>();
		for (Distance distance : dis) {
			points.add(distance.getPoint1());
			points.add(distance.getPoint2());
		}
		int max = -1;
		Iterator<Point> ip = points.iterator();
		while (ip.hasNext()) {
			Point tempP = ip.next();
			if (tempP.getId() > max)
				max = tempP.getId();
		}
		int[] validPoint = new int[points.size()];
		int temp = 0;
		for (Point p : points) {
			validPoint[temp] = p.getId();
			temp++;
		}

		Graph g = new Graph(max);
		for (Distance distance : dis) {
			g.connect(distance.getPoint1().getId(), distance.getPoint2()
					.getId(), distance.getDistance());
		}

		Dijkstra d = new Dijkstra(g, validPoint);

		d.shortestPath(start.getId(), end.getId());

		List<Point> ps = new ArrayList<Point>();

		for (int id : d.getSeq()) {
			for (Point p : points) {
				if (p.getId() == id) {
					ps.add(p);
					continue;
				}
			}
		}
		return ps;
	}


}
